GATE 2009
Question 1 |
Which one of the following in NOT necessarily a property of a Group?
Commutativity
| |
Associativity | |
Existence of inverse for every element
| |
Existence of identity |
Question 1 Explanation:
A Group should satisfy Closure, Associative, should have identity element and each element has inverse.
So, commutativity is not required.
So, commutativity is not required.
Question 2 |
What is the chromatic number of an n-vertex simple connected graph which does not contain any odd length cycle? Assume n ≥ 2.
2 | |
3 | |
n-1 | |
n |
Question 2 Explanation:
If n≥ 2 and there are no odd length cycles, then it is a bipartite graph.
A bipartite graph has the chromatic number 2.
Eg: Consider a square, which has 4 edges. It can be represented as bipartite ,with chromatic number 2.
Eg: Consider a square, which has 4 edges. It can be represented as bipartite ,with chromatic number 2.
Question 3 |
Which one of the following is TRUE for any simple connected undirected graph with more than 2 vertices?
No two vertices have the same degree. | |
At least two vertices have the same degree. | |
At least three vertices have the same degree. | |
All vertices have the same degree.
|
Question 3 Explanation:
Method 1:
If all vertices have different degrees, then the degree sequence will be {1,2,3,....n-1}, it will not have ‘n’( A simple graph will not have edge to itself, so it can have edges with all other (n-1) vertices). Degree sequence has only (n-1) numbers, but we have ‘n’ vertices. So, by Pigeonhole principle there are two vertices which has same degree.
Method 2:
A) Consider a triangle, all vertices has same degree, so it is false
C) Consider a square with one diagonal, there are less than three vertices with same degree, so it is false
D) Consider a square with one diagonal, vertices have different degrees. So, it is false.
We can conclude that option B is correct.
If all vertices have different degrees, then the degree sequence will be {1,2,3,....n-1}, it will not have ‘n’( A simple graph will not have edge to itself, so it can have edges with all other (n-1) vertices). Degree sequence has only (n-1) numbers, but we have ‘n’ vertices. So, by Pigeonhole principle there are two vertices which has same degree.
Method 2:
A) Consider a triangle, all vertices has same degree, so it is false
C) Consider a square with one diagonal, there are less than three vertices with same degree, so it is false
D) Consider a square with one diagonal, vertices have different degrees. So, it is false.
We can conclude that option B is correct.
Question 4 |
Consider the binary relation R = {(x, y), (x, z), (z, x), (z, y)} on the set {x, y, z}. Which one of the following is TRUE?
R is symmetric but NOT antisymmetric
| |
R is NOT symmetric but antisymmetric | |
R is both symmetric and antisymmetric | |
R is neither symmetric nor antisymmetric |
Question 4 Explanation:
Symmetric Relation: A relation R on a set A is called symmetric if (b,a) € R holds when (a,b) € R.
Antisymmetric Relation: A relation R on a set A is called antisymmetric if (a,b)€ R and (b,a) € R then a = b is called antisymmetric.
In the given relation R, for (x,y) there is no (y,x). So, this is not Symmetric. (x,z) is in R also (z,x) is in R, but as per antisymmetric relation, x should be equal to z, where this fails.
So, R is neither Symmetric nor Antisymmetric.
Antisymmetric Relation: A relation R on a set A is called antisymmetric if (a,b)€ R and (b,a) € R then a = b is called antisymmetric.
In the given relation R, for (x,y) there is no (y,x). So, this is not Symmetric. (x,z) is in R also (z,x) is in R, but as per antisymmetric relation, x should be equal to z, where this fails.
So, R is neither Symmetric nor Antisymmetric.
Question 5 |
(1217)8 is equivalent to
(1217)16
| |
(028F)16 | |
(2297)10 | |
(0B17)16 |
Question 5 Explanation:
(1217)8 = (001 010 001 111)2
Divide the bits into groups, each containing 4 bits.
= (0010 1000 1111)2
= (28F)16
Divide the bits into groups, each containing 4 bits.
= (0010 1000 1111)2
= (28F)16
Question 6 |
What is the minimum number of gates required to implement the Boolean function (AB+C) if we have to use only 2-input NOR gates?
2 | |
3 | |
4 | |
5 |
Question 6 Explanation:
NOR is Complement of OR
AB+C
= (A+C)(B+C) ← Distribution of + over
= ((A+C)’+(B+C)’)’
1st NOR- (A+C)’. Let X = (A+C)’
2nd NOR- (B+C)’. Let Y = (B+C)’
3rd NOR- (X+Y)’
AB+C
= (A+C)(B+C) ← Distribution of + over
= ((A+C)’+(B+C)’)’
1st NOR- (A+C)’. Let X = (A+C)’
2nd NOR- (B+C)’. Let Y = (B+C)’
3rd NOR- (X+Y)’
Question 7 |
How many 32K × 1 RAM chips are needed to provide a memory capacity of 256K-bytes?
8 | |
32 | |
64 | |
128 |
Question 7 Explanation:
Each chip capacity = 32K × 1- bit
Needed memory capacity = 256K - bytes = 256K*8 bits
Number of chips needed = 256K*8 / 32K×1 = 64
Needed memory capacity = 256K - bytes = 256K*8 bits
Number of chips needed = 256K*8 / 32K×1 = 64
Question 8 |
A CPU generally handles an interrupt by executing an interrupt service routine
As soon as an interrupt is raised. | |
By checking the interrupt register at the end of fetch cycle. | |
By checking the interrupt register after finishing the execution of the current instruction. | |
By checking the interrupt register at fixed time intervals. |
Question 8 Explanation:
As soon as an interrupt is raised the corresponding register is set. But CPU acts on it only after execution of its current instruction. This is followed to ensure integrity of instructions.
Question 9 |
In which one of the following page replacement policies, Belady’s anomaly may occur?
FIFO | |
Optimal | |
LRU | |
MRU |
Question 9 Explanation:
Belady's anomaly is the phenomenon in which increasing the number of page frames results in an increase in the number of page faults for certain memory access patterns. This phenomenon is commonly experienced when using the first-in first-out.
Question 10 |
The essential content(s) in each entry of a page table is/are
Virtual page number | |
Page frame number | |
Both virtual page number and page frame number | |
Access right information |
Question 10 Explanation:
For every page table it contains page frame number.
Virtual page number can represents index in the page table to get the page frame number.
Virtual page number can represents index in the page table to get the page frame number.
Question 11 |
What is the number of swaps required to sort n elements using selection sort, in the worst case?
θ(n) | |
θ(n log n) | |
θ(n2) | |
θ(n2 logn) |
Question 11 Explanation:
Selection sort – There is no Worst case input for selection sort. Since it searches for the index of kth minimum element in kth iteration and then in one swap, it places that element into its correct position. For n-1 iterations of selection sort, it can have O(n) swaps. Selection Sort does a significant number of comparisons before moving each element directly to its final intended position. At most the algorithm requires N swaps. once we swap an element into place, you never go back again.So it is great for writes O(n) but not so great (at all) for reads — O(n2). It isn’t well-suited to generalized sorting, but might work well in specialized situations like EEPROM (where writes are inordinately expensive).
Question 12 |
S→aSa|bSb|a|b
The language generated by the above grammar over the alphabet {a,b} is the set of
all palindromes. | |
all odd length palindromes. | |
strings that begin and end with the same symbol. | |
all even length palindromes. |
Question 12 Explanation:
From the grammar, we can easily infer that it generates all the palindromes of odd length, for ex: strings {aba, bab, aaa, bbb, ….}
Question 13 |
Which of the following statement(s) is/are correct regarding Bellman-Ford shortest path algorithm?
-
P. Always finds a negative weighted cycle, if one
Q. Finds whether any negative weighted cycle is reachable from the source.
P Only | |
Q Only | |
Both P and Q | |
Neither P nor Q |
Question 13 Explanation:
Bellman-Ford shortest path algorithm is a single source shortest path algorithm. So it can only find cycles which are reachable from a given source, not any negative weight cycle. Consider a disconnected where a negative weight cycle is not reachable from the source at all. If there is a negative weight cycle, then it will appear in shortest path as the negative weight cycle will always form a shorter path when iterated through the cycle again and again.
More Info: The Dijkstra'a algorithm:
--A greedy algorithm
--Works when weights are all non-negative
The bellman ford algorithm: If there is a negative cycle, there is no solution, but negative weight edges are allowed.
– Add this cycle again can always produces a less weight path
---If there is no negative cycle, a shortest path has at most |V|-1 edges
---A dynamic programming algorithm
Note: Dijkastra is faster than Bellman-Ford
More Info: The Dijkstra'a algorithm:
--A greedy algorithm
--Works when weights are all non-negative
The bellman ford algorithm: If there is a negative cycle, there is no solution, but negative weight edges are allowed.
– Add this cycle again can always produces a less weight path
---If there is no negative cycle, a shortest path has at most |V|-1 edges
---A dynamic programming algorithm
Note: Dijkastra is faster than Bellman-Ford
Question 14 |
Let πA be a problem that belongs to the class NP. Then which one of the following is TRUE?
There is no polynomial time algorithm for πA. | |
If πA can be solved deterministically in polynomial time,then P = NP. | |
If πA is NP-hard, then it is NP-complete. | |
πA may be undecidable. |
Question 14 Explanation:
Note: Out of syllabus.
Question 15 |
Which one of the following languages over the alphabet {0,1} is described by the regular expression: (0+1)*0(0+1)*0(0+1)*?
The set of all strings containing the substring 00.
| |
The set of all strings containing at most two 0’s. | |
The set of all strings containing at least two 0’s. | |
The set of all strings that begin and end with either 0 or 1. |
Question 15 Explanation:
Option A is false, as the regular expression generates string “010” which doesn’t have “00” as substring. Option B is false, as we can have the string “000” from the given regular expression, which has more than two 0’s. Option D is false, as we cannot generate the string “01” from the given regular expression and according to option D, string “01” must be generated by regular expression, which clearly shows option D is not correct language as per regular expression.
There are 15 questions to complete.